package com.company.tree;

import com.company.linkedList.ListNode;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

public class BalanceBinarySearchTree {

    public TreeNode root;




    public TreeNode insert(int value){

        TreeNode insertNode = new TreeNode(value);
        if (root == null) {
            root = insertNode;
            return root;
        }

        TreeNode node = root;

        while (true){
            if (node.val > value) {//放在左子树
                if (node.left == null) {
                    node.left = insertNode;
//                    insertType= insertType+0;
                    break;
                }
                node = node.left;//某个节点的左子树


            }else {//放在右子树
                if (node.right == null) {
                    node.right = insertNode;

                    break;
                }
                node = node.right;//某个节点的右子树

            }
        }
//        System.out.println("insert node "+value+"  is bbst "+isBBST(root));

        if (!isBBST(root)) {
//            System.out.println("type "+Integer.toBinaryString(insertType));
            TreeNode firstNotBbstNode = getFirstNotBbstNode(root);
            assert firstNotBbstNode != null;
            int avl = avlOfNode(firstNotBbstNode);
            System.out.println("avl of bad node "+avl);
            if (avl>0) {

            }else {

            }
        }

        return root;
    }

    private void zig(TreeNode badNode){

    }
    private void zag(TreeNode badNode){

    }

    private TreeNode getFirstNotBbstNode(TreeNode root){
        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        TreeNode node = root;
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();

            int avl = avlOfNode(poll);
            if (avl<-1||avl>1) {
                return poll;
            }
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
        }
        return null;
    }

    public TreeNode remove(TreeNode node){
        return root;
    }

    public boolean isBBST(TreeNode root){
        Queue<TreeNode> queue = new LinkedBlockingQueue<>();

        TreeNode node = root;
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode poll = queue.poll();

            int avl = avlOfNode(poll);
            if (avl<-1||avl>1) {
                return false;
            }
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
        }
        return true;
    }

    public int avlOfNode(TreeNode node){
        assert node!=null;

        int depthOfLeft = depthOfNode(node.left);
        int depthOfRight = depthOfNode(node.right);
        int avl = depthOfLeft - depthOfRight;
        return avl;
    }

    private int depthOfNode(TreeNode root){
        if (root == null) {
            return 0;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;

        int leftDepth = depthOfNode(left);
        int rightDepth = depthOfNode(right);

        return 1+Math.max(leftDepth,rightDepth);
    }

}
